package com.jia.explore.dynamicprogramming.knapsack;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-09-01 10:59
 */
public class Dy_12 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int N = 1010;
        int[] vs = new int[N];
        int[] ws = new int[N];
        int[][] f = new int[N][N];
        for(int i = 1; i <= n; i++) {
            vs[i] = scanner.nextInt();
            ws[i] = scanner.nextInt();
        }
        //f[i][j] 表示i到最后一个物体体积最大为j的最大价值， 为了打印不倒序而已
        //那么f[i][j] = f[i+1][j]不选第i个物品，还有一种情况f[i][j] = f[i+1][j - v] + w //选第i个物品  f[1][m]最大
        for (int i = n; i > 0; i--) {
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i + 1][j];
                if (j >= vs[i]) {
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - vs[i]] + ws[i]);
                }
            }
        }
        //f[1][m]为最大，对于第一个物品是否选中通过判断，f[1][m] == f[2][m - vs[1]] + w[1]
        //如果f(1,m)=f(2,m−v[1])+w[1]，说明选取了第1个物品可以得到最优解。
        //
        //如果f(1,m)=f(2,m)，说明不选取第一个物品才能得到最优解。
        //
        //如果f(1,m)=f(2,m)=f(2,m−v[1])+w[1]，说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品。
        int cur_m = m;
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if(i == n && cur_m>= vs[i]) {
                sb.append(i);
                break;
            }
            if(cur_m >= vs[i] && (f[i][cur_m] == f[i+1][cur_m - vs[i]] + ws[i]) ) {
                //System.out.println("--" + i + " " + cur_m + "vs[i]:" + vs[i] + "ws[i]:"+ws[i]);
                sb.append(i + " ");
                cur_m -= vs[i];
            }
        }
        System.out.println(sb.toString());
    }
}
